#include "iostream"
#include "assert.h"
#include "queue"
#include "list"

using ElemType = char;

struct TreeNode
{
    ElemType data;
    TreeNode *left;
    TreeNode *right;

    // 构造
    ////////////////////////////////////////////////////////////////////
    static TreeNode *create()
    {
        auto r = (TreeNode *)malloc(sizeof(TreeNode));
        *r = TreeNode();
        return r;
    }
    static TreeNode *create(ElemType data)
    {

        auto r = (TreeNode *)malloc(sizeof(TreeNode));
        r->data = data;
        r->left = nullptr;
        r->right = nullptr;
        return r;
    }
    static TreeNode *create(ElemType data, TreeNode *l, TreeNode *r)
    {

        auto ret = (TreeNode *)malloc(sizeof(TreeNode));
        ret->data = data;
        ret->right = r;
        ret->left = l;
        return ret;
    }
    static TreeNode *create(TreeNode *l, TreeNode *r)
    {

        auto ret = (TreeNode *)malloc(sizeof(TreeNode));
        ret->right = r;
        ret->left = l;
        return ret;
    }
    //

    // 遍历
    ////////////////////////////////////////////////////////////////////
    void level_iter()
    {
        std::queue<TreeNode *> queue;
        auto node = this;
        queue.push(node);
        int level = 0;
        while (!queue.empty())
        {
            auto a = queue.front();
            queue.pop();
            TreeNode *first_push = nullptr;
            if (a->left)
            {
                queue.push(a->left);
                first_push = a->left;
            }
            if (a->right)
            {
                queue.push(a->right);
                if (!first_push)
                    first_push = a->right;
            }

            // //这一段比较重要，需要记一下
            // if (a == node) //取出来的a==这一层最后一个元素
            // {
            //     printf("%d\r\n", level);
            //     level++;
            //     if (!queue.empty())
            //     {
            //         node = queue.back();
            //         //因为是再这一层最后一个元素的前提下，xieg
            //         // 所以队列的最后一个元素就是下一层最后一个元素
            //     }
            // }

            //换个思路
            if (a == node) //取出来的是这层第一个元素
            {
                printf("\r\n%d ", level);
                level++;
                node = first_push;
            }

            printf("%c,", a->data);
        }
        printf("\r\n");
    }
    //
};

TreeNode *handle(ElemType A[], ElemType B[], int &Abegin, int Bbegin, int Bend)
{
    if (Bbegin > Bend)
    {
        return nullptr;
    }
    auto node = TreeNode::create();
    if (Bbegin == Bend)
    {
        node->data = B[Bbegin];
        Abegin++;
        return node;
    }

    int i = Bbegin;
    for (; i <= Bend; i++)
    {
        if (A[Abegin] == B[i])
        {
            break;
        }
    }
    //用完 abegin，为下一次++
    Abegin++;
    node->data = B[i];
    node->left = handle(A, B, Abegin, Bbegin, i - 1);
    node->right = handle(A, B, Abegin, i + 1, Bend);
    return node;
}

TreeNode *construct(TreeNode *tree)
{
    std::list<TreeNode *> stack;
    auto p = tree;
    TreeNode *head_p = nullptr;
    TreeNode *last_p = nullptr;
    while (p || !stack.empty())
    {
        if (p)
        {
            printf("qianxu %c\r\n", p->data);
            //此处操作即为前序
            if (p->right == nullptr && p->left == nullptr)
            {
                if (last_p)
                {
                    last_p->right = p;

                    if (!head_p)
                    {
                        head_p = last_p;
                    }
                }
                //叶子节点
                last_p = p;
            }
            stack.push_back(p);
            p = p->left; //一路向左
        }
        else
        {
            auto p1 = stack.back();
            stack.pop_back();
            //此处操作即为中序
            p = p1->right;
        }
    }
    return head_p;
}

void main()
{
    //   a
    //  / \
    // b   c
    // |\  | \
    // d e f  g
    //
    // 正序: a b d e c f g
    // 中序: a d b e f c g

    ElemType A[] = {'a', 'b', 'd', 'e', 'c', 'f'};
    ElemType B[] = {'d', 'b', 'e', 'a', 'f', 'c'};

    int abegin = 0;
    auto tree = handle(A, B, abegin, 0, 5);

    // tree->level_iter();

    auto t_link = construct(tree);
    while (t_link)
    {
        printf("%c\r\n", t_link->data);
        t_link = t_link->right;
    }
    // t_link->level_iter();
}